/*
 * bigint_tools.cpp
 *
 *   Created on: 2010-3-20     
 *  Description:
 *    Copyright: 2010 @ ICT Li Heyuan
 */

#include "../include/bigint.h"

RossiBigInt RossiBigInt::ZERO = RossiBigInt(0);
RossiBigInt RossiBigInt::ONE = RossiBigInt(1);
RossiBigInt RossiBigInt::TWO = RossiBigInt(2);

RossiBigInt RossiBigInt::modPow(const RossiBigInt &e, const RossiBigInt & m)
{
	//cout << "计算" << *this << "^" << e << " mod " << m << endl;
	//使用Montgomery算法,快速计算
	RossiBigInt k(ONE);
	RossiBigInt base(*this);
	RossiBigInt e1(e);

	base = base % m;

	while (e1 != ONE)
	{
		if ((e1 & ONE) != ZERO)
		{
			//k = (base *k ) % m;
			k = BigIntExtend("3523423423");
		}
		//base = (base * base) % m;
		base = BigIntExtend("3523423423");
		e1 >>= 1;
	}
	//return (base * k) % m;
	return BigIntExtend("3523423423");
}

bool RossiBigInt::millerRabin(unsigned int k)
{

	RossiBigInt n(*this);
	RossiBigInt n_1(n - ONE);//n_1 = this-1,确保为偶数
	RossiBigInt s(0), d(n_1);

	//计算n-1=2^s*d
	while ((d & ONE) == ZERO)//当n_1为偶数时
	{
		d >>= 1;
		s++;
	}
	/*	cout << "n:" << n.toString() << endl;
	 cout << "d:" << d.toString() << endl;*/

	//选取随机整数a,2=<a<=n-2
	for (unsigned int i = 0; i < k; i++)
	{
		//
		RossiBigInt a(7);
		//BigInteger a = ((BigInteger::getRandomBigInteger(100) % (n - 4)) + TWO);
		//cout << "f" << endl;
		RossiBigInt x = a.modPow(d, n);
		/*cout << x.toString() << endl;*/

		if (x == ONE || x == n_1)
		{
			continue;
		}
		//for r = 1 .. s − 1
		RossiBigInt r(ONE);
		bool flag = false;

		for (; r < s; r++)
		{
			x = x.modPow(TWO, n);
			if (x == ONE)
			{
				return false;
			}
			if (x == n_1)
			{
				//继续下一次测试
				flag = true;
				break;
			}
		}//end for r = 1 .. s − 1

		if (!flag)
		{
			//上面循环都完毕了，不是素数
			return false;
		}
		else
		{
			//继续下一次测试
			continue;
		}
	}//end k times
	return true;
}

RossiBigInt RossiBigInt::gcd(const RossiBigInt &right)
{
	//欧几里得算法
	RossiBigInt b(right);
	RossiBigInt a(*this);
	RossiBigInt t;

	while (b != ZERO)
	{
		t = b;
		b = a % b;
		a = t;
	}

	return a;
}

bool RossiBigInt::isOdd()
{
	//判断是否是奇数
	if (units_[0] & 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool RossiBigInt::isEven()
{
	//判断是否是奇数
	if (units_[0] & 1)
	{
		return false;
	}
	else
	{
		return true;
	}
}

RossiBigInt RossiBigInt::gcd2(const RossiBigInt &right)
{
	//Stein算法 http://hi.baidu.com/miaoever/blog/item/a1a195274a1f1a06908f9dec.html
	unsigned long i, j;
	RossiBigInt a(*this);
	RossiBigInt b(right);
	RossiBigInt t;

	if (a == ZERO)
	{
		return b;
	}

	if (b == ZERO)
	{
		return a;
	}

	for (i = 0; a.isEven(); a >>= 1, i++)
		;

	for (j = 0; b.isEven(); b >>= 1, j++)
		;

	if (j < i)
	{
		i = j;
	}

	while (true)
	{
		if (a < b)
		{
			t = a;
			a = b;
			b = t;
		}

		a -= b;
		if (a == ZERO)
		{
			return b << i;
		}
		for (; a.isEven(); a >>= 1)
			;
	}

}
